UVA1218 Perfect Service

一道很不错的树形dp。

dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0,表示uu为服务器,那么uu的儿子和父亲既可以是服务器,也可以不是。

阅读全文 »

CF767C Garland

首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。

记所有点权和为sumsum

容易想到,令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 , 则有转移:

阅读全文 »

SP9934 ALICE - Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

UVA1500 Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

P4056 [JSOI2009]火星藏宝图

首先有一个非常 naive 的 O(n2)\mathcal{O(n^2)} dp。

dpidp_i 表示到第 ii 座岛的最大收益,那么有:

dpi=max1jn,j=i,xjxi,yjyi{dpj(xixj)2(yiyj)2}+vidp_i=\max_{1\le j \le n, j \not= i ,x_j \le x_i ,y_j \le y_i }\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+v_i

阅读全文 »

P2120 [ZJOI2007]仓库建设

did_i 为工厂 ii 到工厂 nn (山底)的距离, dpidp_i 为在第 ii 个工厂建仓库的最小花费。

因为只能向下运,所以第 nn 个工厂必须建仓库存放它自己的产品,答案便为 dpndp_n

边界条件 dp0dp_0 为不建仓库的花费。

阅读全文 »

P3648 [APIO2014]序列分割

dp[t][i]=max{dp[t1][j]+sj(sisj)}dp[t][i]=\max\{dp[t-1][j] + s_j(s_i-s_j)\}

dp[t][i]=max{dp[t1][j]+sjsisj2}dp[t][i]=\max\{dp[t-1][j] + s_js_i-s_j^2\}

阅读全文 »